package com.bh.数组问题讲解;

import java.awt.*;
import java.util.HashMap;
import java.util.Map;

/**
 * @author ：HB
 * @date ：Created in 2021/8/29 21:49
 * @description：给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
 */
public class 两数之和1 {
    public static void main(String[] args) {
//        int[] nums = {2, 7, 11, 15};
//        int target=9;
//        int[] nums = {2, 3, 4, 15};
//        int target=6;
        int[] nums = {3, 3, 4, 15};
        int target = 6;
        int[] ints = twoNumSum2(nums, target);
        for (int index : ints) {
            System.out.println("index = " + index);
        }
    }


    public static int[] twoNumSum1(int[] nums, int target) {
        int outPut[] = new int[2];
        // 双重for O(n^2)
        // 优化：使用Arrays.sort() 先对数组进行排序。底层使用的是快排O(nlgn)
        Label:
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length - 1; j++) {
                if (nums[i] + nums[j] == target) {
                    outPut[0] = i;
                    outPut[1] = j;
                    break Label;
                }
            }

        }
        return outPut;
    }

    private static int[] twoNumSum2(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();

// 遍历数组，全部保存到 hashmap中
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);
        }

        int[] outPut = new int[2];
// 遍历数组，挨个查找对应的“那个数”在不在map中
        for (int i = 0; i < nums.length; i++) {
            int thatNum = target - nums[i];
            if (map.get(thatNum) != i && map.containsKey(thatNum)) {
                outPut[0] = i;
                outPut[1] = map.get(thatNum);
                return outPut;
            }

        }
        throw new IllegalArgumentException("No two sum solution");
    }
}
